package main

import (
	"container/heap"
	"fmt"
)

// 这题有些类似跳跃游戏，使用贪心的算法
// 抽象出来就是 min(apples[i], days[i]), 代表当前位置能跳跃的最大距离
// 然后求出跳跃最远的位置。 并去除掉 0，当天不吃的数量
// [2,1,10]
// [2,10,1] 测试用例不通过。 第二天的苹果可以吃10天，所以跳跃游戏的思路不正确！！
func eatenApples(apples []int, days []int) int {
	cnt := 0
	start := 0
	end := start + min(apples[0], days[0])
	for start < len(apples) {
		maxStep := end
		for ; start <= end && start < len(apples); start++ {
			maxStep = max(maxStep, min(apples[start], days[start])+start)
		}
		// 循环结束，start = end， end 要等于新的，最远位置
		end = maxStep
		if end < start {
			end = start
			cnt += 1
		}
	}
	return end - cnt
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// 官方的实现是使用优先队列
// 贪心的思想，优先吃掉离过期最近的苹果。
func eatenApples1(apples, days []int) (ans int) {
	h := hp{}
	i := 0
	for ; i < len(apples); i++ {
		for len(h) > 0 && h[0].end <= i {
			heap.Pop(&h)
		}
		if apples[i] > 0 {
			heap.Push(&h, pair{i + days[i], apples[i]})
		}
		if len(h) > 0 {
			h[0].left--
			if h[0].left == 0 {
				heap.Pop(&h)
			}
			ans++
		}
	}
	for len(h) > 0 {
		for len(h) > 0 && h[0].end <= i {
			heap.Pop(&h)
		}
		if len(h) == 0 {
			break
		}
		p := heap.Pop(&h).(pair)
		num := min(p.end-i, p.left)
		ans += num
		i += num
	}
	return
}

// 实现一些方法
type pair struct{ end, left int }
type hp []pair

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].end < h[j].end }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

// 尾部添加
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }

// 尾部删除
func (h *hp) Pop() interface{} { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

//func main() {
//	apples := []int{3,0,0,0,0,2}
//	days := []int{3,0,0,0,0,2}
//	rst := eatenApples(apples, days)
//	fmt.Println(rst)
//}
